package a10_动态规划;

/**
 * <p>
 * a12_背包理论基础2
 * </p>
 *
 * @author flyduck
 * @since 2025/2/10
 */
public class a12_背包理论基础2 {
    public static void main(String[] args) {
        ///////////////////////////////////////
//        Scanner scanner = new Scanner(System.in);
//
//        int number = scanner.nextInt();
//        int totalWeight = scanner.nextInt();
//
//        int[] weightArray = new int[number];
//        int[] valueArray = new int[number];
//
//        for (int i = 0; i < weightArray.length; i++) {
//            weightArray[i] = scanner.nextInt();
//        }
//
//        for (int i = 0; i < valueArray.length; i++) {
//            valueArray[i] = scanner.nextInt();
//        }

        ////////////////////////////////////////


        int number = 6;
        int totalWeight = 1;

        int[] weightArray = new int[]{2,2,3,1,5,2};
        int[] valueArray = new int[]{2,3,1,5,4,3};

        int[] dp = new int[totalWeight + 1];
        dp[0] = 0;

        for (int i = 0; i < number; i++) {
            for (int j = totalWeight; j >= 1; j--) {
                if(j >= weightArray[i]){
                    dp[j] = Math.max(dp[j],dp[j-weightArray[i]] + valueArray[i]);
                }
            }
        }

        System.out.println(dp[totalWeight]);



        //物品   重量    价值
        //物0     1       15
        //物1     3       20
        //物2     4       30
        //   0  1  2  3  4
        //0  0  15 15 15 15
        //1  0
        //2  0

        //滚动数组：将上一层数组拷贝下来了

        //dp[j]含义：容量为j的背包所能装的最大价值为dp[j]

        //递推公式：
        // 不放物品i：dp[j]
        // 放物品i: dp[j-weight[i]] + value[i]
        // dp[j] = Math.max(dp[j],dp[j-weight[i]] + value[i])

        //初始化：
        // dp[0]=0：背包容量为0所能放的最大价值
        // 非0的应该初始化成多少
        // 因为dp[j] = Math.max(dp[j],dp[j-weight[i]] + value[i])，所以刚开始需要将dp[j]初始化成非负数里面的最小值就行了，即为0

        //遍历顺序
        //for()//物品正序
        // for()//背包倒叙***

        //为什么要倒叙：
        //首先是滚动函数，所以依赖于当前层的当前节点和前面的节点，如果先计算前面的节点，之前的值就被覆盖了

        //一维数组必须先遍历物品再遍历重量



    }
}
